#ifndef _GRAPH_CLASS_H
#define _GRAPH_CLASS_H


#include <limits.h>
#include <string>
#include <unordered_map>
#include <vector>
#include <unordered_set>
#include <assert.h>
#include <iostream>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include "DisjointSet.h"


#define MAXVERTICES (128)

// TODO - Documentation
//
// Pipe Goals - Bellman Ford?
using namespace std;


class Vertex {
 public:
  int idx;
  string label;
  int minDist;
  Vertex(string label) {
    this->label = label;
   }
  ~Vertex() {  }
};


class Edge {
 public:
  int weight;
  string label;
  Vertex * src;
  Vertex * dest;
  ~Edge() {  }
  
  Edge(Vertex * src, Vertex * dest, int weight = 1, string label = "") {
    this->src = src;
    this->dest = dest;
    this->weight = weight;
    this->label = label;
  }


  
  bool operator<(Edge other) const {
    return weight < other.weight;
  }
  bool operator>(Edge other) const {
    return weight > other.weight;
  }
  bool operator<=(Edge other) const {
    return weight <= other.weight;
  }
  bool operator>=(Edge other) const {
    return weight >= other.weight;
  }
};

class EdgeComparator {
 public:
  bool operator()(const Edge* e1, const Edge* e2) {
    return e1->weight < e2->weight;
  }
};


class VertexComparator {
 public:
  bool operator()(const Vertex* v1, const Vertex* v2) {
    return v1->minDist < v2->minDist;
  }
};


class Graph {

  public: 
  virtual ~Graph() {  }

  virtual void insertEdge( string src, string  dest, int weight = 1, string label = "" ) = 0;
  virtual void removeEdge( string src, string  dest ) = 0;
  virtual int containsEdge( string  src, string dest ) = 0;

  virtual int containsVertex (string ID) = 0;
  virtual Vertex * insertVertex( string label = "" ) = 0;
  virtual void removeVertex( string vertex ) = 0;

  virtual Edge * getEdge(string src, string dest) = 0;

  virtual vector < Vertex * > * getNeighbors( string src ) = 0;
  virtual vector < Edge * > * getOutgoingEdges( string src ) = 0;
  virtual vector < Edge * > * getIncomingEdges( string src ) = 0;
  virtual Vertex * getVertex(string v) = 0;
  virtual int consistencyCheck() = 0;
  virtual int size() = 0;

  virtual vector < Vertex * > * getAllVertices() = 0;
  virtual vector < Edge * > * getAllEdges() = 0;

  // Returns a map containing vertex labels as keys and number of
  // edges between start and that vertex as values
  virtual unordered_map <string, string >* BFS( string start ) {
    if (this->containsVertex( start )) {
      unordered_map<string, string> * toRet = new unordered_map<string, string>;
      vector < Vertex * > * vertices = this->getAllVertices();
      while (vertices->size() > 0) {
	Vertex * tmp = vertices->back();
	vertices->pop_back();
	toRet->insert(make_pair(tmp->label, "None" ));
      }
      delete vertices;

      toRet->find(start)->second = "Origin";
      queue<string> * q = new queue<string>;
      q->push(start);
      
      while ( q->size() > 0 ) {
	string cur = q->front();
	q->pop();
	vector< Vertex *> * neighbors = this->getNeighbors(cur);
	while ( neighbors->size() > 0 ) {
	  string tmp = neighbors->back()->label;
	  neighbors->pop_back();
	  if ( toRet->find(tmp)->second == "None"  ) {
	    // Vertex not yet discovered
	    toRet->find(tmp)->second = cur;
	    q->push(tmp);
	  }
	}
	delete neighbors;
      }
      
      delete q;
      return toRet;
    }
    else {
      return NULL;
    }
    return NULL;
  }

  // Returns a map containing vertex labels as keys and prior vertex
  // labels as values. So, this would allow determination of paths
  virtual unordered_map <string, string >* DFS( string start ) {
    if (this->containsVertex( start )) {
      unordered_map<string, string> * toRet = new unordered_map<string, string>;
      vector < Vertex * > * vertices = this->getAllVertices();
      while (vertices->size() > 0) {
	Vertex * tmp = vertices->back();
	vertices->pop_back();
	toRet->insert(make_pair(tmp->label, "None"));
      }
      delete vertices;

      toRet->find(start)->second = "Origin";
      stack<string> * q = new stack<string>;
      q->push(start);
      
      while ( q->size() > 0 ) {
	string cur = q->top();
	q->pop();
	vector< Vertex *> * neighbors = this->getNeighbors(cur);
	while ( neighbors->size() > 0 ) {
	  string tmp = neighbors->back()->label;
	  neighbors->pop_back();
	  if ( toRet->find(tmp)->second == "None"  ) {
	    // Vertex not yet discovered
	    toRet->find(tmp)->second = cur;
	    q->push(tmp);
	  }
	}
	delete neighbors;
      }
      delete q;
      return toRet;
    }
    else {
      return NULL;
    }
    return NULL;
  }

  vector< string > * TopologicalOrdering( ) {
    vector < Vertex * > * vertices = this->getAllVertices();
    stack < Vertex * >* noIncoming = new stack<Vertex *>;
    unordered_map < Vertex *, int > * inCounts = new unordered_map < Vertex *, int>;
    vector < string > * toRet = new vector<string>;
    for (int i = 0; i < vertices->size(); i++) {
      vector < Edge *> * tmp = getIncomingEdges(vertices->at(i)->label);
      inCounts->insert(make_pair(vertices->at(i), tmp->size()));
      if (tmp->size() == 0) {
	noIncoming->push(vertices->at(i));
      }
      delete tmp;
    }

    while ( noIncoming->size() > 0 ) {
      Vertex * tmp = noIncoming->top();
      toRet->push_back(tmp->label);
      noIncoming->pop();
      
      // Get the outgoing edges, and decrement all of those vertex counts
      vector< Edge * > * outgoing = getOutgoingEdges(tmp->label);
      for (int i = 0; i < outgoing->size(); i++) {
	inCounts->find(outgoing->at(i)->dest)->second = inCounts->find(outgoing->at(i)->dest)->second - 1;
	if ( inCounts->find(outgoing->at(i)->dest)->second == 0 ) {
	  noIncoming->push( outgoing->at(i)->dest );
	}
      }
      delete outgoing;
    }

    if (toRet->size() == this->size() ) {
      delete vertices;
      delete noIncoming;
      delete inCounts;
      return toRet;
    }
    delete vertices;
    delete noIncoming;
    delete inCounts;
    delete toRet;
    return NULL;

  }

  

  // Returns a unordered_map where keys are vertex ID strings and values are 
  // prior vertex ID strings in the shortest path from start to each vertex.
  unordered_map< string, string> * Dijkstra(string start) {
    if (this->containsVertex(start) ) {
      //set< Edge*, EdgeComparator > * pq = new set< Edge*, EdgeComparator >;
      set < Vertex*, VertexComparator > * pq = new set <Vertex *, VertexComparator>;
      unordered_map< string, string> * toRet = new unordered_map<string, string>;
      unordered_map< string, Vertex *> * dict = new unordered_map<string, Vertex *>;
      unordered_map< Vertex *, bool > * accepted = new unordered_map<Vertex *, bool >;
      vector < Vertex * > * vertices = this->getAllVertices();
      for (int i = 0; i < vertices->size(); i++) {
	toRet->insert(make_pair( (vertices->at(i))->label, "None") );
	vertices->at(i)->minDist = INT_MAX;
	pq->insert ( vertices->at(i) );
	dict->insert(make_pair( (vertices->at(i))->label, vertices->at(i))  );
	accepted->insert( make_pair( vertices->at(i), false ) );
      }
      toRet->find(start)->second = "Origin";
      Vertex * tmp = dict->find(start)->second;
      pq->erase(tmp);
      tmp->minDist = 0;
      pq->insert(tmp);
      accepted->find(tmp)->second = true;
      
      while ( pq->size() > 0 ) {
	Vertex * next = *(pq->begin());
	pq->erase(pq->begin());
        accepted->find(next)->second = true;
	vector < Edge * > * out = getOutgoingEdges( next->label );
	int dist = next->minDist;
	for (int i = 0; i < out->size(); i++) {
	  if ( accepted->find( out->at(i)->dest )->second == false ) {
	    
            int curWt = out->at(i)->dest->minDist;
	    int altWt = dist + out->at(i)->weight;
            if (curWt > altWt) {
	      pq->erase( out->at(i)->dest );
	      out->at(i)->dest->minDist = altWt;
	      toRet->find( out->at(i)->dest->label )->second = out->at(i)->src->label;
	      pq->insert( out->at(i)->dest );
	    }
	  }
	}
	delete out;
      }
      delete dict;
      delete pq;
      delete vertices;
      delete accepted;
      return toRet;
    }

    return NULL;
    
  }
  
  vector < Edge * > * KruskalMST() {
    
    vector < Edge * > * edges = this->getAllEdges();
    map < int, Edge * > * pq = new map < int, Edge * >;
    for ( int i = 0; i < edges->size(); i++) {
      pq->insert(make_pair( edges->at(i)->weight, edges->at(i) ) );
    }
    delete edges;
    map < Vertex *, DisjointSet<Vertex*> *> * sets = new map < Vertex *, DisjointSet<Vertex*> *>;
    vector < Vertex * > * vertices = this->getAllVertices();
    for ( int i = 0; i < vertices->size(); i++) {
      sets->insert( make_pair (vertices->at(i), new DisjointSet<Vertex*>( vertices->at(i) ) ) );
    }
    delete vertices;
    
    vector < Edge * > * toRet = new vector<Edge *>;
    while ( toRet->size() < this->size() - 1 && pq->size() > 0 ) {
      Edge * tmp = pq->begin()->second;
      pq->erase(pq->begin());
      DisjointSet<Vertex*> * first = sets->find(tmp->src)->second;
      DisjointSet<Vertex*> * second = sets->find(tmp->dest)->second;
      if ( ! first->sameSet(second) ) {
	toRet->push_back(tmp);
	first->Union(second);
      }
    }
    
    for ( auto it = sets->begin(); it != sets->end(); it ++ ) {
      delete it->second;
    }
    delete sets;
    delete pq;
    return toRet;
  }
  
  vector < Edge * > * PrimMST( string start ) {
    if ( ! this->containsVertex( start ) ) {
      return NULL;
    }
    map < int, Edge *> * pq = new map < int, Edge *>;
    vector < Edge * > * toRet = new vector < Edge * >;
    unordered_set < Vertex * > * discovered = new unordered_set < Vertex * >;

    vector < Edge * > * out = this->getOutgoingEdges(start);
    for (int i = 0; i < out->size() ; i++) {
      pq->insert( make_pair(out->at(i)->weight, out->at(i)) );
    }
    delete out;
    
    discovered->insert( this->getVertex(start) );

    while ( toRet->size() < this->size() - 1 and pq->size() > 0 ) {
      Edge * e = pq->begin()->second;
      pq->erase( pq->begin() );
      if ( discovered->find( e->dest ) == discovered->end() ) {
        discovered->insert( e->dest );
        toRet->push_back(e);
        vector < Edge * >* tmp = this->getOutgoingEdges( e->dest->label );
        for (int i = 0; i < tmp->size(); i++) {
          pq->insert( make_pair(tmp->at(i)->weight, tmp->at(i) ));
        }
        delete tmp;
      }
    }
    delete pq;
    delete discovered;
    return toRet;

  }

  int BellmanFord( string src, unordered_map< string, int > * distances, unordered_map< string, string> * priors ) {

    if ( ! priors or ! distances or ! this->containsVertex(src) ) {
      return -1;
    }

    vector < Vertex * > *vertices = this->getAllVertices();
    for (int i = 0; i < vertices->size(); i++) {
      // Overflow ?? 
      distances->insert( make_pair( vertices->at(i)->label, INT_MAX/10 ) );
      priors->insert( make_pair( vertices->at(i)->label, "" ) );
    }
    distances->find( getVertex( src )->label )->second = 0;
    int size = vertices->size();
    int negCyc = 0;

    for ( int i = 0; i < size; i++) {
      for (int j = 0; j < size; j++ ) {
        string v1 = vertices->at(j)->label;
        for (int k = 0; k < size; k++ ) {
          string v2 = vertices->at(k)->label;
          if ( this->containsEdge( v1, v2 ) ) {
            int wt = this->getEdge ( v1, v2 ) -> weight;
            if ( distances->find( v1 )->second + wt < distances->find( v2 )->second ) {
              distances->find(v2)->second = distances->find(v1)->second + wt;
              priors->find(v2)->second = v1;
              if ( i == size - 1 ) {
                negCyc = 1;
              }
            }
          }
        }
      }
    }
    delete vertices;
    return negCyc;
  }


// Bellman Ford high level descriptions
//
// Maintain an array for each vertex. Actually, maintain a pair of arrays
// One array has at the ith index the shortest distance to i found so far
// The other has the prior vertex in the shortest path to i
// Finally, an unordered map can do the mapping of Vertex * to index
// Or, maybe have 2 unordered maps
//
// Then, iterate through the vertices n-1 times, each time comparing each vertex to 
// every other vertex and computing the distance. If it's shorter, update the distance
// and the prior vertices
//
// Detect a negative cycle by running it an nth time. Return 1 if there is a negative
// cycle or 0 otherwise. 
  

    


};

#endif
